/*
	排序
*/
/*
	1 直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2
                            移动次数 最少0； 最多(n-1)(n+4)/2
                           使用一个辅助存储空间，是稳定的排序；

	2 折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
                移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
                使用一个辅助存储空间，是稳定的排序；

	3 冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);
                      移动次数最少为0，最多时间复杂度表示为O(n2);
                        使用一个辅存空间，是稳定的排序；

	4 简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;
                            移动次数最少为0，最多为3(n-1);
                             使用一个辅存空间，是稳定的排序；

	5 快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);
                    比较和移动次数最多的时间复杂度表示为O(n2);
                    使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

	6 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);
                  使用一个辅存空间，是不稳定的排序；
*/

//插入排序
/*
	当最好的情况，如果原来本身就是有序的，
	比较次数为n-1次（分析（while (j >= 0 && temp < R[j])）这条语句）,
	时间复杂度为O(n)。
	当最坏的情况，原来为逆序，
	比较次数为2+3+...+n=(n+2)(n-1)/2次，
	而记录的移动次数为i+1(i=1,2...n)=(n+4)(n-1)/2次。
	如果序列是随机的，根据概率相同的原则，平均比较和移动的次数为n^2/4.
*/
void insertsort(int *A, int n)
{
	int i,j;
	//for(dk = n/2;dk>=1;dk=dk/2)
	for(i = 2;i<=n;i++)
	{//dk+1	
		if(A[i]<A[i-1])//i-dk
		{
			A[0] = A[i];
			for(j = i-1;A[j]>A[0];j--)//i-dk
				A[j+1] = A[j];//j+dk
			A[j+1] = A[0];//j+dk
		}
	}
}

//折半插入
void insertsort(int *A，int n)
{
	int i,j,low,high,mid;
	for(i=2;i<=n;i++)
	{
		A[0] = A[i];
		low = 1; high = i-1;
		while(i<=j)
		{
			mid = (low+high)/2;
			if(A[mid]>A[0])
				high = mid-1;
			else
				low = mid+1;
		}

		for(j = i-1;A[j]>=high+1;j--)
			A[j+1] = A[j];

		A[high+1] = A[0];
	}
}

/*
	选择排序不关心表的初始次序，
	它的最坏情况的排序时间与其最佳情况没多少区别，
	其比较次数都为 n(n-1)/2，交换次数最好的时候为0，
	最差的时候为n-1，尽管和冒泡排序同为O(n)，但简单选择排序性能上要优于冒泡排序。
*/
//双向冒泡
void BubbleSort(int *A, int n)
{
	int low=0,high=n-1;
	bool  flag = true;

	while(low<high&&flag)
	{
		flag = false;
		for(i = low;i<high;i++)
		{
			if(A[i]>A[i+1])
				swap(A[i],A[i+1]);
			flag = true;
		}
		high--;
		for(i = high;i>low;i--)
		{
			if(A[i]<A[i-1])
				swap(A[i],A[i-1])
				flag = true;
		}
		low++;
	}
}

/*
	输入一个正整数数组，将数组中的各整数连接排成一个大整数，
	输出能排出的所有整数中最小的一个
*/
int bi(int x)
{//计算位数
	int i = 0;
	while(x)
	{
		x=x/10;
		i++;
	}
	return i;
}
int ex(int p,int x)
{
	int i,s=1;
	for(i=1;i<=x;i++)
	{
		s=s*p;
	}
	return s;
}
void min(int *A, int n)
{
	int i,j,m,l,flag = 0,tmp;
	for(j=0;j<n;j++)
	{
		flag = 0;

		for(i = 0;i<n-1;i++)
		{
			m = bi(A[i]);
			l = bi(A[i+1]);
			if(A[i]*ex(10,l)+A[i+1]>A[i+1]*ex(10,m)+A[i])
				swap(A[i],A[i+1]);
				flag = 1;
		}

		if(flag==0)
			break;
	}
}

/*
	堆排序
*/
void Buildmaxheap(int *A, int n)
{
	for(int i = len/2;i>0;i--)
	{
		adjustdown(A,i,n);
	}
}

void adjustdown(int *A, int k, int n)
{
	A[0] = A[k];
	for(int i = k*2;i<=n;i = i*2)
	{
		if(A[i]<A[i+1]&&i<n)
			i++;
		if(A[0]>A[i])
			break;
		else
			A[k] = A[i];
			k = i;
	}
	A[k] = A[0];
}

void adjustup(int *A, int k)
{
	A[0] = A[k];
	int i = k/2;
	while(i>0&&A[i]<A[0])
	{
		A[k] = A[i];
		k=i;
		i=k/2;
	}
	A[k] = A[0];
}

/*
	快速排序
*/
void quicksort(int *A, int p, int r)
{
	if(p<r)
	{
		int q = partition(A,p,r);
		quicksort(A,p,q-1);
		quicksort(A,q+1,r);
	}
}

int partition(int *A, int p ,int r)
{
	int x = A[p];
	int i = p, j = r+1;

	while(1)
	{
		while(i<j&&A[i]<x) i++;
		while(A[j]>x) j++;

		if(i>=j)
			break;
		swap(A[i],A[j]);
	}

	A[p] = A[j];
	A[j] = x;

	return j;
}


/*
	设待排序整数序列中有一半是奇数，一半是偶数，
	设计算法重排这些整数，使得所有奇数位于奇数下标位置，所有偶数位于偶数下标位置
*/
void jo(int A[],int n)
{//将长度为n的数组A（一半为奇数一半为偶数）的奇偶数放在对应奇偶下标
	int i=0,j=n-1,temp;
	while(i<n&&j>0)
	{
		while(A[i]%2==0) i+=2;
		while(A[j]%2==1) j-=2;
		temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	}
}

//利用队列实现杨辉三角的构造
void san(int n)
{
	int Q[1000];
	int f=0,r=0;
	Q[r++]=1;
	int i,j,x,y;
	for(i=2;i<=n;i++)
	{
		x=Q[f++];
		Q[r++]=1;
		for(j=i-2;j>0;j--)
		{
			y=Q[f++];
			Q[r++]=x+y;
			x=y;
		}
		Q[r++]=1;
	}
	for(i=1;i<=n;i++) 
	{
		for(j=i*(i-1)/2;j<i*(i-1)/2+i;j++)
			printf("%d ",Q[j]);
		printf("\n");
	}
}

//写出在中序线索二叉树里查找指定结点下后序的前驱结点的算法
/*
	1.在后序序列种,p有右子女,右子女是前驱,没有右子女有左子女,左子女是前驱
	2.如果左右子女均无,p是某个祖先结点f的右子树按中序遍历的第一个节点,如果f有左子女,左子女是后序的前驱,   (左中右 ，左右中)
	3.f无左子女,找到某个有左子女的祖先结点g,g的左子女是p在后序的前驱,没找到则p是后序遍历的第一个节点
	4.如果p的lchild为空,p为中序第一个节点,p的前驱也为空
*/
BiThrTree InPostpre(BiThrTree T,BiThrTree p)
{
	BiThrTree q;
	if(p->rtag == 0)//p有右子女
		q = p->rchild;
	else if(p->ltag = 0)//p无只有左子女
		q = p->lchild;
	else if(p->lchild == NULL)//p是中序遍历第一个结点,即最左边
		q = NULL;
	else
	{
		while(p->ltag==1&&p->lchild != NULL)
			p = p->lchild;
		if(p->ltag == 0)
			q = p->lchild;	
		else
			q = NULL;
	}

	return q;

}

BiThrTree InPostpost(BiThrTree T,BiThrTree p)
{
	while(p->rflag) //is a child node
  		p=p->rchild;
	r=p->rchild;  //r is p's father
	if(r->rchild==p||!r->rflag) return r; 
	p=r->rchlid;
	while(p->lchild||p->rchild)
	{
		if(p->lchild) {p=p->lchild;continue}
		if(p->rchild)  p=p->rchild;
	}
	return p;

}
	
/*
	给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
	注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
	二叉树采用的三叉链表存储的，包含其父节点
 */
/*
	1.如果p有右子树,则其后继结点是右子树的按中序遍历的第一个节点
	2.p没有右子树,是双亲的左子女,其双亲是其后继结点
	3.p没有右子树,是双亲的右子树,后继为父节点的父节点,直到父节点有左孩子,其左孩子是后继
	4.没找到即p是最后一个
*/

typedef struct Bitree
{
	int data;
	struct Bitree *Lchild, *Rchild, *father;
};

Bitree inordernext(Bitree *T, Bitree *p)
{
	if(p==NULL)
        return NULL;
    if(p->right!=NULL)
    {
        p=p->right;
        while(p->left!=NULL)
            p=p->left;
        return p;
    } 
    
    while(p->father!=NULL)
    {
        TreeLinkNode *root=p->father;
        if(root->left==p)
           	return root;
        p=p->father;
    }
    
    return NULL;
}

//找中序线索二叉树的，p结点的直接前驱
BiThrTree Inpre(BiThrTree p)
{
	BiThrTree pre;
	if(p->Ltag==1)
		pre = p->lchild;
	else
	{
		for(q = p->lchild; q->Rtag == 0;q=q->rchild)
			pre = q;
	}

	return pre;
}

//找中序线索二叉树的，p结点的直接后驱
BiThrTree Innext(BiThrTree p)
{
	BiThrTree next;
	if(p->Rtag == 1)
		next = p->rchild;
	else
	{
		for(q=r->rchild;q->Ltag==0;q=q->lchild)
			next = q;
	}

	return next;
}

//先序线索二叉树找后继
BiThrTree PreNext(BiThrTree p)
{
	BiThrTree next;
	if(p->Rtag == 1)
		next = p->rchild;
	else if(p->lchild)
		next = p->lchild;
	else
		next = p->rchild;

	return next;
}

//后续线索二叉树找前驱
BiThrTree PostPre(BiThrTree p)
{
	BiThrTree pre;
	if(p->ltag==1)
		pre = p->lchild;
	else if(p->rchild)
		pre = p->rchild;
	else
		pre = p->lchild;

	return pre;
}

/*
	给定一个未排序的整数数组，找到第一个缺失的正整数 您的算法应在O（n）
	如果A[i]是正数 并且A[i]<n 就把 它 放到i-1的位置上.
	这样遍历一遍数组，如果A[i]不等于它的下标加1 就是第一个缺失的正数
*/

/*
	二叉树遍历（已知前序和后序遍历，求中序遍历的可能的序列数）
*/

for(i=0;i<lengthA;i++)
	
	  for(j=1;j<lengthB;j++)
	
	   if(a[i]==b[j]&&a[i+1]==b[j-1])
	
	    count++;
	
	 printf("%d\n",power(ans));
	 return 0;

int power(int ans)
{
	int sum=1;
	while(--ans>=0) sum*=2;
	return sum;
}

/*
	在柱状图中找最大的矩形：给一组非负的整数来表示一个柱状图，
	设计一个算法找到最大 面积的能适合到柱状图内的矩形
*/